// # Dynamic programming + Dichotomy.
//     class Solution:
//     def lengthOfLIS(self, nums: [let]) -> let:
//     tails, res = [0] * len(nums), 0
// for num in nums:
// i, j = 0, res
// while i < j:
// m = (i + j) // 2
// if tails[m] < num: i = m + 1 # 如果要求非严格递增，将此行 '<' 改为 '<=' 即可。
// else: j = m
// tails[i] = num
// if j == res: res += 1
// return res
//
// 作者：jyd
// 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
//     来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

let lengthOfLIS = function (nums) {
    let dp = new Array(nums.length);
    dp.fill(1, 0, nums.length);

    for (let i = 1; i < nums.length; i++)
        for (let j = 0; j < i; j++)
            nums[i] > nums[j] && (dp[i] = Math.max(dp[i], dp[j] + 1))
    return nums.length < 2 ? nums.length : Math.max(...dp)
};


let lengthOfLIS01 = function (nums) {
    let top = new Array(nums.length);
    for (let i = 0; i < nums.length; i++) {
        top[i] = 0;
    }

    // 牌堆数初始化为 0
    let piles = 0;

    for (let i = 0; i < nums.length; i++) {
        // 要处理的扑克牌
        let poker = nums[i];

        /***** 搜索左侧边界的二分查找 *****/
        let left = 0, right = piles;
        while (left < right) {
            // 记住这里要向下取整
            let mid = Math.floor((left + right) / 2);
            if (top[mid] > poker) {
                right = mid;
            } else if (top[mid] < poker) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        /*********************************/

        // 没找到合适的牌堆，新建一堆
        left === piles && piles++;

        // 把这张牌放到牌堆顶
        top[left] = poker;
    }

    console.log(top);

    // 牌堆数就是 LIS 长度
    return piles;
}

lengthOfLIS01([10, 9, 2, 5, 3, 7, 101, 18])